#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class node_t
{
public:
    node_t(int v, int i): val(v), index(i), count(0){};
    int val;
    int index;
    int count;
};


class stack_t 
{
public:
   stack_t(){};
   vector<node_t *> heap; 
   map<int, node_t *> nodeMap;
   void heapify(vector<node_t *> &heap);
   void push(int num);
   int pop();
};

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void heapify2(vector<node_t *> &A, int index)
{
    if (index == 1) return;
    int size = A.size(); 
    int left = 2*index, right = 2*index+1;
    int largest = index;

    if (left <= size && A[left-1]->count > A[index-1]->count) {
	largest = left;
    }
    if (right <= size && A[right-1]->count > A[largest-1]->count) {
	largest = right;
    }

    if (largest != index) {
        int tmp = A[index-1]->index;
        A[index-1]->index = A[largest-1]->index;
        A[largest-1]->index = tmp;
	swap(A[index-1], A[largest-1]);
        heapify2(A, largest);
    }
}

void siftDown(vector<node_t *> &A, int index)
{
    int size = A.size(); 
    int left = 2*index, right = 2*index+1;
    int largest = index;

    if (left <= size && A[left-1]->count > A[index-1]->count) {
	largest = left;
    }
    if (right <= size && A[right-1]->count > A[largest-1]->count) {
	largest = right;
    }

    if (largest != index) {
        int tmp = A[index-1]->index;
        A[index-1]->index = A[largest-1]->index;
        A[largest-1]->index = tmp;
	swap(A[index-1], A[largest-1]);
        siftDown(A, largest);
    }
}

void siftUp(vector<node_t *> &A, int index)
{
    if (index == 1) return;
    int size = A.size(); 
    int parent = index/2;
    int largest = parent;

    if (A[largest-1]->count < A[index-1]->count) {
        int tmp = A[index-1]->index;
        A[index-1]->index = A[largest-1]->index;
        A[largest-1]->index = tmp;
	swap(A[index-1], A[largest-1]);
        siftUp(A, largest);
    }
}
void stack_t::heapify(vector<node_t *> &heap)
{
    for (int i = heap.size(); i>=1; i--) {
	heapify2(heap, i);
    }
}

void stack_t::push(int num)
{
    cout << "Push: " << num << " ";
    if (nodeMap.count(num) == 0) {
	node_t *node = new node_t(num, heap.size()+1);
        heap.push_back(node);
        nodeMap[num] = node; 
    } 
    nodeMap[num]->count++;
    siftUp(heap, heap.size());
    for (int i = 0; i < heap.size(); i++)
	cout << "(" << heap[i]->val << "," << heap[i]->count << " " << heap[i]->index << ")" << " ";
    cout << endl;
    //getchar();
}

int stack_t::pop()
{
    if (heap.size() == 0) return 0;

    cout << "Before pop: " ;
    for (int i = 0; i < heap.size(); i++)
	cout << "(" << heap[i]->val << "," << heap[i]->count << " " << heap[i]->index << ")" << " ";
    cout << endl;
    node_t *top = heap[0];
    int rtn = top->val;
    top->count--;
    cout << "Before heapify: " ;
    for (int i = 0; i < heap.size(); i++)
	cout << "(" << heap[i]->val << "," << heap[i]->count << " " << heap[i]->index << ")" << " ";
    cout << endl;
    siftDown(heap, top->index);
    cout << "After heapify: " ;
    for (int i = 0; i < heap.size(); i++)
	cout << "(" << heap[i]->val << "," << heap[i]->count << " " << heap[i]->index << ")" << " ";
    cout << endl;
    if (top->count == 0) {
        nodeMap.erase(top->val);
	heap.erase(heap.begin() + heap.size()-1);
    }

    //getchar();

    return rtn;
}


int main(int argc, char **argv)
{
    stack_t myStack;
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(2);
    myStack.push(2);
    myStack.push(2);
    myStack.push(1);
    myStack.push(1);
    myStack.push(1);
    myStack.push(1);
    myStack.push(1);
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
    cout << myStack.pop() << endl;
}
